/** 
 * \file CGUITreeCtrl.cpp
 * \brief File CGUITreeCtrl.cpp is taken from irrlicht forum. Tree class is created by Veylon.
 * link: http://irrlicht.sourceforge.net/phpBB2/viewtopic.php?t=17422&highlight=cguitreectrl
 * I changed that tree code little bit to suite my needs.
 * Big thanks to Veylon.
 */

#include "CGUITreeCtrl.h"
#include "IGUIEnvironment.h"
#include "IGUIFont.h"
#include "IVideoDriver.h"
#include "CGlobals.h"
#include "CUserInterface.h"
#include "CLevelEditor.h"
#include "DoUndoCommands.h"
#include "CListBox.h"
#include "CEventReceiver.h"
#include "IGUIContextMenu.h"
#include "CMultiCommand.h"
#include "CChangeTreeParentCommand.h"
#include "CSetVisibleCommand.h"
#include "ISceneManager.h"
#include "ISceneNode.h"
#include "IrrlichtDevice.h"
//#include <algorithm>

extern CGlobals* g;
extern CLevelEditor* editor;
extern CUserInterface* ui;

using namespace irr;
using namespace gui;
using namespace core;

#define ROOT_ID -1

IGUITreeCtrl *irr::gui::AddGUITreeCtrl(
		IGUIEnvironment *env,
		const core::rect<s32> Rectangle,
		IGUIElement *parent,
		s32 id
)
{
	if(parent == NULL)
		parent = env->getRootGUIElement();
	CGUITreeCtrl *tree = new CGUITreeCtrl(env, parent, id, Rectangle);
	return tree;
}
CGUITreeCtrl::~CGUITreeCtrl()
{
	ScrollBarH->drop();
	ScrollBarV->drop();
	if(Font)
		Font->drop();
	Clear();
	delete RootNode;
	IDList.clear();
}

CGUITreeCtrl::CGUITreeCtrl(IGUIEnvironment* environment, IGUIElement* parent, s32 id, core::rect<s32> rectangle):
IGUITreeCtrl(environment, parent, id, rectangle),
NumItems(0),
Selected(1),
Font(NULL),
OverrideFont(NULL),
video(environment->getVideoDriver())
{
	m_picked = false;
	m_SavedNode = 0;
	RootNode = new TreeNode;
	RootNode->Parent = NULL;
	RootNode->Child = NULL;
	RootNode->Sibling = NULL;
	RootNode->ID = ROOT_ID;
	RootNode->Text = stringw("Root Node");
	RootNode->SceneObject = 0;
	RootNode->Open = true;
	
	IDList.set_sorted(true);
	IDList.push_back(ROOT_ID);
	
	ScrollBarV = Environment->addScrollBar(
		false,
		core::rect<s32>(RelativeRect.getWidth() - Environment->getSkin()->getSize(EGDS_SCROLLBAR_SIZE), 0, RelativeRect.getWidth(), RelativeRect.getHeight() - Environment->getSkin()->getSize(EGDS_SCROLLBAR_SIZE)),
		this
	);
	ScrollBarH = Environment->addScrollBar(true,
		core::rect<s32>(0,RelativeRect.getHeight() - Environment->getSkin()->getSize(EGDS_SCROLLBAR_SIZE), RelativeRect.getWidth()-Environment->getSkin()->getSize(EGDS_SCROLLBAR_SIZE), RelativeRect.getHeight()),
		this
	);
	ScrollBarH->setPos(0);
	ScrollBarV->setPos(0);
	recalculateItemHeight();
//	Font = Environment->getSkin()->getFont();
}

TreeNode *CGUITreeCtrl::FindNode(s32 ID)
{
	if(ID == ROOT_ID)
		return NULL;	// Don't find root node!
	bool FromChild = false;
	for(TreeNode *CurNode = RootNode; CurNode; CurNode = GetNextNode(CurNode))
		if(CurNode->ID == ID)
			return CurNode;
	return NULL;
}
TreeNode *CGUITreeCtrl::GetNextNode(TreeNode *node)
{
	// Try Child
	if(node->Child)
		return node->Child;
	// Try Sibling
	else if(node->Sibling)
		return node->Sibling;
	// Go down ancestor tree until we find a sibling
	while(node->Parent && !node->Sibling)
		node = node->Parent;
	if(node->Sibling)
		return node->Sibling;
	else
		return NULL;			// Bust
}
TreeNode *CGUITreeCtrl::GetNextVisibleNode(TreeNode *node)
{
	// Try Child
	if(node->Child && SubtreeVisible(node))
		return node->Child;
	// Try Sibling
	else if(node->Sibling)
		return node->Sibling;
	// Go down ancestor tree until we find a sibling
	while(node->Parent && !node->Sibling)
		node = node->Parent;
	if(node->Sibling)
		return node->Sibling;
	else
		return NULL;			// Bust
}
TreeNode *CGUITreeCtrl::GetPrevNode(TreeNode *node)
{
	if(!node->Parent)
		return NULL;
	if(node->Parent->Child != node)	// Later Sibling. Return previous
	{
		TreeNode *prev = node->Parent->Child;
		while(prev->Sibling != node)
			prev = prev->Sibling;
		if(prev->Child)	// Get last child of previous
		{
			prev = prev->Child;
			bool Last = false;
			while(prev->Sibling || prev->Child)
			{
				if(prev->Sibling)
					prev = prev->Sibling;
				else if(prev->Child)
					prev = prev->Child;
			}
			return prev;
		}
		else	// Previous sibling has no children. Return it
		{
			return prev;
		}
	}
	else if(node->Parent->Child == node)	// Only Child. Return parent
		return node->Parent;
	else
		return NULL;	// No previous
/*	Horrible Inefficient Old Way
	TreeNode *prev = RootNode;
	TreeNode *next;
	next = GetNextNode(prev);
	while(next && next != node)
	{
		prev = next;
		next = GetNextNode(prev);
	}
	if(next)
		return prev;
	else
		return NULL;
*/
}
TreeNode *CGUITreeCtrl::GetPrevVisibleNode(TreeNode *node)
{
	if(node->Parent->Child != node)	// Later Sibling. Return previous
	{
		TreeNode *prev = node->Parent->Child;
		while(prev->Sibling != node)
			prev = prev->Sibling;
		if(prev->Child && SubtreeVisible(prev))	// Get last child of previous
		{
			prev = prev->Child;
			bool Last = false;
			while(prev->Sibling || (prev->Child && SubtreeVisible(prev)))
			{
				if(prev->Sibling)
					prev = prev->Sibling;
				else if(prev->Child && SubtreeVisible(prev))
					prev = prev->Child;
			}
		}
		return prev;
	}
	else if(node->Parent->Child == node)	// Only Child. Return parent
	{
		if(node->Parent == RootNode)
			return NULL;
		return node->Parent;
	}
	else
		return NULL;	// No previous
/*	Inefficient Old Way
	if(node == RootNode)	// Only one that doesn't have a previous
		return false;
	TreeNode *prev = RootNode;
	TreeNode *next;
	next = GetNextNode(prev);
	while(next && next != node)
	{
		prev = next;
		next = GetNextVisibleNode(prev);
	}
	if(next)
		return prev;
	else
		return NULL;
*/
}
TreeNode *CGUITreeCtrl::InsertNode(core::stringw Text, TreeNode *parent, s32 id, CSceneObject *SceneObject, bool Checked,bool Locked)
{
	// Root node is parent, if none other
	if(!parent)
		parent = RootNode;
	// Make ID if none
	/*if(id == 0)
	{
		s32 i = IDList.size();
		while(IDList.binary_search(i) != -1)
		{
			i++;
			if(i>=MAX_NODES)
			{
				i -= MAX_NODES;
			}
		}
		id = i;
	}*/
	// Duplicate ID, quit
	if(IDList.binary_search(id) != -1)
		return NULL;
	TreeNode *newnode = new TreeNode;
	newnode->Child = NULL;
	newnode->Parent = parent;
	newnode->Sibling = NULL;
	newnode->ID = id;
	newnode->SceneObject = SceneObject;
	newnode->Text = Text;
	newnode->LowerText = Text;
	newnode->LowerText.make_lower();
	newnode->Open = false;
	newnode->Checked = Checked;
	newnode->Locked = false;

	if(!parent->Child)	// Childless parent is simple
	{
		parent->Child = newnode;
	}
	else
	{
		TreeNode *curnode = parent->Child;
		while(curnode->Sibling)
			curnode = curnode->Sibling;
		curnode->Sibling = newnode;
		// Find last sibling of parent and include new sibling
	}
	// Tidy up
	NumItems++;
	IDList.push_back(id);
	recalculateScrollBars();
	return newnode;
}
bool CGUITreeCtrl::ChangeParent(TreeNode *node, TreeNode *newparent)
{
	if(!node)				// We have to move SOMETHING
		return false;
	if(node == RootNode)	// Heavens No!
		return false;
	if(!newparent)			// No go.
		return MoveToRoot(node);
	if(newparent == node->Parent)	// What would be the point?
		return true;	// There! Done.
	if(IsParent(newparent, node))
		return false;

	// Sever old ties
	CutTies(node);
	// Insert self into new situation
	node->Parent = newparent;	// We have a new parent, no matter what
	node->Sibling = NULL;	// We're the last, no matter what
	// Is the parent childless?
	if(!newparent->Child)
	{
		newparent->Child = node;
	}
	// Otherwise, put ourselves at the end of the list
	else
	{
		TreeNode *lastnode = newparent->Child;
		while(lastnode->Sibling)
			lastnode = lastnode->Sibling;
		lastnode->Sibling = node;
	}
	recalculateScrollBars();
	// OK, all good
	return true;
}

bool CGUITreeCtrl::IsParent(TreeNode *node, TreeNode *parent)
{
	if(!node || !parent)
		return false;

	while(node->Parent)
	{
		if(node->Parent == parent)
			return true;
		node = node->Parent;
	}

	return false;
}

gui::TreeNode * CGUITreeCtrl::GetSiblingPrevNode(TreeNode *pSelf)
{
	TreeNode * pParentNode = pSelf->Parent;
	TreeNode * childNode = pParentNode->Child;
	if( childNode == NULL )
	{
		return NULL;
	}

	if( childNode == pSelf )
	{
		return NULL;
	}
	
	while( childNode->Sibling != pSelf )
	{
		childNode = childNode->Sibling;			
	}
	return childNode;
}

void CGUITreeCtrl::MovePos(TreeNode *pSelf, bool isMovePrev , bool gotoTop)
{
	if( gotoTop )
	{
		TreeNode *pPrevNode = GetSiblingPrevNode( pSelf );
		if( pPrevNode == NULL )
		{
			return;
		}

		pPrevNode->Sibling = pSelf->Sibling;
		TreeNode * pParentNode = pSelf->Parent;
		TreeNode * childNode = pParentNode->Child;
		pParentNode->Child = pSelf;
		pSelf->Sibling = childNode;
		return;
	}

	if( isMovePrev )
	{
		TreeNode *pPrevNode = GetSiblingPrevNode( pSelf );
		if( pPrevNode == NULL )
		{
			return;
		}

		TreeNode *pPrevNode2 = GetSiblingPrevNode( pPrevNode );

		if( pPrevNode2 )
		{
			pPrevNode2->Sibling = pSelf;			
		}
		else
		{
			pSelf->Parent->Child = pSelf;
		}

		TreeNode * pNextNode = pSelf->Sibling;
		pSelf->Sibling = pPrevNode;
		pPrevNode->Sibling = pNextNode;
	}
	else
	{
		TreeNode *pNextNode = pSelf->Sibling;
		if( pNextNode == NULL  )
		{
			return;
		}
		if( pSelf->Parent->Child == pSelf )
		{
			pSelf->Parent->Child = pNextNode;
		}
		else
		{
			TreeNode *pPrevNode = GetSiblingPrevNode(pSelf);
			if( pPrevNode )
			{
				pPrevNode->Sibling = pNextNode;
			}
		}

		TreeNode * pNextNode2 = NULL;
		pNextNode2 = pNextNode->Sibling;
		pNextNode->Sibling = pSelf;		
		pSelf->Sibling = pNextNode2;
	}
	recalculateScrollBars();
}

bool CGUITreeCtrl::MoveToRoot(TreeNode *node)
{
	return ChangeParent(node, RootNode);
}

bool CGUITreeCtrl::DeleteNode(TreeNode *node, bool deleteObject)
{
	if(!node)				// No can do
		return false;
	if(node == RootNode)	// Noooo!!!!!
		return false;
	int posInSelected = Selected.binary_search(node);
	if (posInSelected >= 0)
		Selected.erase(posInSelected);
	// Deal with child nodes
	while(node->Child)
	{
		DeleteNode(node->Child, true);
	}
	CutTies(node);
	// Kill our ID from the list
	s32 Offset = IDList.binary_search(node->ID);
	if(Offset != -1)
		IDList.erase(Offset);
	delete node;
	NumItems--;
	recalculateScrollBars();
	return true;
}

void CGUITreeCtrl::Clear()
{
	while(RootNode->Child)
		DeleteNode(RootNode->Child);
}
void CGUITreeCtrl::draw()
{
	if(!IsVisible)
		return;

	recalculateItemHeight(); // if the font changed

	IGUISkin* skin = Environment->getSkin();
	irr::video::IVideoDriver* driver = Environment->getVideoDriver();

	core::rect<s32>* clipRect = 0;
	clipRect = &AbsoluteClippingRect;

	// draw background
	core::rect<s32> frameRect(AbsoluteRect);

	skin->draw3DSunkenPane(this, skin->getColor(EGDC_3D_HIGH_LIGHT), true,
		true, frameRect, clipRect);
	
	// draw items

	core::rect<s32> clientClip(AbsoluteRect);
	clientClip.UpperLeftCorner.Y += 1;
	clientClip.UpperLeftCorner.X += 1;
	clientClip.LowerRightCorner.X -= skin->getSize(EGDS_SCROLLBAR_SIZE)+1;
	clientClip.LowerRightCorner.Y -= skin->getSize(EGDS_SCROLLBAR_SIZE)+1;

	if (clipRect)
		clientClip.clipAgainst(*clipRect);
	
	// Our frame
/*
	frameRect = AbsoluteRect;
	frameRect.UpperLeftCorner.X += 1;
	frameRect.LowerRightCorner.X = AbsoluteRect.LowerRightCorner.X - skin->getSize(EGDS_SCROLLBAR_SIZE);
	frameRect.LowerRightCorner.Y = AbsoluteRect.UpperLeftCorner.Y + ItemHeight;

	frameRect.UpperLeftCorner.Y -= ScrollBar->getPos();
	frameRect.LowerRightCorner.Y -= ScrollBar->getPos();
*/
	
	if(RootNode->Child)	// No point in drawing anything otherwise
	{
		core::rect<s32> *MyClip = NULL;		
		core::array<bool> DistStack;
		u32 Indent = 1-ScrollBarH->getPos()/10;
		s32 Count = 0;
		video::SColor colblk = skin->getColor(gui::EGDC_BUTTON_TEXT);
		TreeNode *node = RootNode->Child;
		bool FromChild = false;
		while(node)	// If we're at the root node, then we're done
		{
			s32 DistCount = Count - ScrollBarV->getPos()/10;
			
			bool inSearchString = m_searchText.size() == 0 || node->LowerText.find(m_searchText.c_str()) != -1 ;
			if (!inSearchString)
				--Count;

			if(DistCount >= 0 && inSearchString)
			{
				// Stop drawing
				if((DistCount+1) * ItemHeight > RelativeRect.getHeight())
				{
					break;
				}
				else/* if((DistCount+2) * ItemHeight > RelativeRect.getHeight())*/
				{
					MyClip = &clientClip;
				}
				s32 offset = 0;
				// Get Origin
				// = ItemWidth to the left of the text
				core::position2d<s32> Origin = AbsoluteRect.UpperLeftCorner + core::position2d<s32>((Indent-1)*ItemHeight, DistCount * ItemHeight);
				video::SColor col;
				if (Selected.binary_search(node) >= 0)
				{
					col = skin->getColor(gui::EGDC_HIGH_LIGHT_TEXT);
				}
				else
				{
					col = skin->getColor(gui::EGDC_BUTTON_TEXT);
				}
				// Draw Lines
				if(node->Parent != RootNode)
				{
					// Horizontal
					if(node->Child)	// Accomodate Square
					{
						DrawHorizontalLine(
							Origin + core::position2d<s32>(-Frac12, Frac12),
							Frac12 + Frac18,
							colblk, MyClip);
					}
					else	// No Need
					{
						DrawHorizontalLine(
							Origin + core::position2d<s32>(-Frac12, Frac12),
							Frac12,
							colblk, &clientClip);
					}
					// Vertical
					if(node->Sibling)
					{
						DrawVerticalLine(
							Origin + core::position2d<s32>(-Frac12, 0),
							ItemHeight,
							colblk, MyClip);
					}
					else
					{
						DrawVerticalLine(
							Origin + core::position2d<s32>(-Frac12, 0),
							Frac12,
							colblk, MyClip);
					}
					// Vertical Far left lines
					for(u32 l = 0; l < DistStack.size()-1; l++)
					{
						if(DistStack[DistStack.size() - l - 1])
						{
							DrawVerticalLine(
								Origin - core::position2d<s32>((l+1)*ItemHeight + Frac12,0),
								ItemHeight,
								colblk, &clientClip);
						}
						/*	Red lines for debugging
						else
						{
							Draw2DLine(
								Origin - core::position2d<s32>((l+1)*ItemHeight + Frac12+1, 0),
								Origin - core::position2d<s32>((l+1)*ItemHeight + Frac12+1, -ItemHeight),
								video::SColor(0xFFFF0000), clientClip);
						}
						*/
					}	
				}
				// Square, Plus sign if closed
				core::position2d<s32> UpperLeft, UpperRight, LowerLeft;
				if(node->Child && Indent > 0)
				{
					UpperLeft = Origin + core::position2d<s32>(Frac14, Frac14);
					UpperRight = Origin + core::position2d<s32>(Frac34, Frac14);
					LowerLeft = Origin + core::position2d<s32>(Frac14, Frac34);
					if(node->Open)	// Draw bottom line to match up
					{
						//DrawVerticalLine(
						//	Origin + core::position2d<s32>(Frac12 + 2, Frac34),
						//	Frac14, colblk, MyClip);
						//Draw minus sign
						DrawHorizontalLine(
							Origin + core::position2d<s32>(Frac14, Frac12),
							SqSize, col, MyClip);
					}
					else
					{
						// Draw Plus Sign
						// Horizontal
						DrawHorizontalLine(
							Origin + core::position2d<s32>(Frac14, Frac12),
							SqSize, col, MyClip);
						// Vertical
						DrawVerticalLine(
							Origin + core::position2d<s32>(Frac12, Frac14),
							SqSize, col, MyClip);
					}
					// Draw Square (After, so it covers up and looks nice
					DrawVerticalLine(UpperLeft, SqSize, col, MyClip);
					DrawHorizontalLine(UpperLeft, SqSize, col, MyClip);
					DrawVerticalLine(UpperRight, SqSize, col, MyClip);
					DrawHorizontalLine(LowerLeft, SqSize, col, MyClip);
				}
				offset = ItemHeight;

				//draw visible check box
				UpperLeft = Origin + core::position2d<s32>(Frac18 + offset, Frac18);
				UpperRight = Origin + core::position2d<s32>(Frac78 + offset, Frac18);
				LowerLeft = Origin + core::position2d<s32>(Frac18 + offset, Frac78);

				if (!node->Child)
				{
					--MyClip->UpperLeftCorner.X;
					if (Indent == 1)
					{
						DrawHorizontalLine(Origin + core::position2d<s32>(1, Frac12), Frac14 - 1 + SqSize, colblk, MyClip);
					}
					else
					{
						DrawHorizontalLine(Origin + core::position2d<s32>(0, Frac12), Frac14 + SqSize, colblk, MyClip);
					}
					++MyClip->UpperLeftCorner.X;
				}

				if(node->Checked)
				{
					DrawChecked(UpperLeft, CheckBoxSize, col, MyClip);
				}

				DrawVerticalLine(UpperLeft, CheckBoxSize, col, MyClip);
				DrawHorizontalLine(UpperLeft, CheckBoxSize, col, MyClip);
				DrawVerticalLine(UpperRight, CheckBoxSize, col, MyClip);
				DrawHorizontalLine(LowerLeft, CheckBoxSize, col, MyClip);
				offset += ItemHeight;
				
				if(Selected.binary_search(node) >= 0)
				{
					video->draw2DRectangle(skin->getColor(EGDC_ACTIVE_BORDER),core::rect<s32>(Origin + core::position2d<s32>(offset,0), Origin + core::position2d<s32>(ItemHeight + Font->getDimension(node->Text.c_str()).Width+offset-ItemHeight+ 5,ItemHeight)), &clientClip);
				}
				Font->draw(node->Text.c_str(),
					core::rect<s32>
					(	AbsoluteRect.UpperLeftCorner.X + (Indent-1)*ItemHeight + offset + 3,
						AbsoluteRect.UpperLeftCorner.Y + DistCount * ItemHeight,
						AbsoluteRect.LowerRightCorner.X - skin->getSize(EGDS_SCROLLBAR_SIZE),
						AbsoluteRect.UpperLeftCorner.Y + (DistCount+1) * ItemHeight
					), col, false, false, MyClip);
			}
			// And we get the next node
			// Try Child
			if(node->Child && SubtreeVisible(node))
			{
				if(node->Sibling)
					DistStack.push_back(true);
				else
					DistStack.push_back(false);
				Indent++;
				node = node->Child;
			}
			// Try Sibling
			else if(node->Sibling)
			{
				node = node->Sibling;
			}
			// Go down ancestor tree until we find a sibling
			else
			{
				while(node->Parent && !node->Sibling)
				{
					node = node->Parent;
					Indent--;
					if(node != RootNode)
						DistStack.erase(DistStack.size()-1);
				}
				if(node->Sibling)
					node = node->Sibling;
				else
					break;
			}
			Count++;
		}
		s32 itemVisible =  Count - RelativeRect.getHeight() / ItemHeight + 1;
		if(itemVisible < 0)
		{
			itemVisible = 0;
			ScrollBarV->setMax(10 * itemVisible);	
		}
		else
		{
			s32 MaxItems =  NumItems - RelativeRect.getHeight() / ItemHeight + 1;
			if(MaxItems < 0)
			MaxItems = 0;
			ScrollBarV->setMax(10 * MaxItems);
		}
	}

	if(m_picked && Selected.size() > 0)
	{
		position2d<s32> pos = g->device->getCursorControl()->getPosition();
		pos += m_pickedOffset;
		for (u32 i = 0; i < Selected.size(); ++i)
		{
			rect<s32> rect;
			rect.UpperLeftCorner = pos;
			rect.LowerRightCorner = pos + position2d<s32>(Font->getDimension(Selected[i]->Text.c_str()).Width, ItemHeight);
			video->draw2DRectangle(skin->getColor(EGDC_ACTIVE_BORDER), rect, &clientClip);
			Font->draw(Selected[i]->Text.c_str(), rect, skin->getColor(gui::EGDC_HIGH_LIGHT_TEXT), false, false, &clientClip);
			pos += position2di(0, ItemHeight);
		}
	}

	IGUIElement::draw();
}
void CGUITreeCtrl::DrawHorizontalLine(core::position2d<s32> start, s32 length, video::SColor &color, const core::rect<s32> *ClipRect)
{
	// Line can't be draw here
	if(ClipRect)
	{
		if(!ClipRect->isPointInside(start))
			return;
		if(start.X + length > ClipRect->LowerRightCorner.X)
			length = ClipRect->LowerRightCorner.X - start.X;
	}
	rect<s32> r (start , start + core::position2d<s32>(length,1));
	video->draw2DRectangle(color , r );
		//(start, start + core::position2d<s32>(length,0), color);
}
void CGUITreeCtrl::DrawVerticalLine(core::position2d<s32> start, s32 length, video::SColor &color, const core::rect<s32> *ClipRect)
{
	// Line can't be draw here
	if(ClipRect)
	{
		if(!ClipRect->isPointInside(start))
			return;
		if(start.Y + length > ClipRect->LowerRightCorner.Y)
			length = ClipRect->LowerRightCorner.Y - start.Y;
	}
	rect<s32> r (start , start + core::position2d<s32>(1 , length));
	video->draw2DRectangle(color , r );
	//video->draw2DLine(start, start + core::position2d<s32>(0,length), color);
}
void CGUITreeCtrl::DrawChecked(core::position2d<s32> start, s32 length, video::SColor &color, const core::rect<s32> *ClipRect)
{
	// Line can't be draw here
	if(ClipRect)
	{
		if(!ClipRect->isPointInside(start))
			return;
		//if(start.Y + length > ClipRect->LowerRightCorner.Y)
		//	length = ClipRect->LowerRightCorner.Y - start.Y;
	}
	s32 third = length * 1/3;
	s32 third2 = length * 2/3;
	rect<s32> r (start  + core::position2d<s32>(third , third) , start + core::position2d<s32>(third2 , third2));
	video->draw2DRectangle(color , r );

	//video->draw2DLine(start, start + core::position2d<s32>(length,length), color);
	//video->draw2DLine(start + core::position2d<s32>(0,length), start + core::position2d<s32>(length,0), color);
}
void CGUITreeCtrl::recalculateItemHeight()
{
	IGUISkin* skin = Environment->getSkin();
	if(
		(OverrideFont && Font != OverrideFont)
		||
		(!OverrideFont && Font != skin->getFont())
	)
	{
		if (Font)
			Font->drop();

		if(OverrideFont)
			Font = OverrideFont;
		else
			Font = skin->getFont();
		ItemHeight = 0;

		if (Font)
		{
			ItemHeight = Font->getDimension(L"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789").Height;
			// The squares look better
			// When itemheight is divisible by 4 or 8
			
			if(ItemHeight % 8)
				ItemHeight += 8-(ItemHeight % 8);

			Frac18 = ItemHeight/8;
			Frac14 = ItemHeight/4;
			Frac12 = ItemHeight/2;
			Frac34 = ItemHeight*3/4;
			Frac78 = ItemHeight*7/8;
			
			CheckBoxSize = ItemHeight - Frac18 * 2;
			SqSize = ItemHeight - Frac14 * 2;
			Font->grab();
			recalculateScrollBars();
		}
	}

//	TotalItemHeight = ItemHeight * Items.size();
//	ScrollBar->setMax(TotalItemHeight - AbsoluteRect.getHeight());
}

void CGUITreeCtrl::recalculateScrollBars()
{
	s32 MaxItems =  NumItems - RelativeRect.getHeight() / ItemHeight + 1;
	if(MaxItems < 0)
		MaxItems = 0;
	ScrollBarV->setMax(10 * MaxItems);

	int maxdepth = 0;
	for (TreeNode* node = RootNode; node; node = GetNextNode(node))
	{
		maxdepth = MAX(maxdepth, GetDepth(node));
	}

	ScrollBarH->setMax(10 * (maxdepth + 8));
}

void CGUITreeCtrl::CutTies(TreeNode *node)
{
	// Only Child
	if(node->Parent->Child == node && !node->Sibling)
	{
		node->Parent->Child = NULL;
	}
	// First Child
	else if(node->Parent->Child == node && node->Sibling)
	{
		node->Parent->Child = node->Sibling;
	}
	// Last Child
	else if(node->Parent->Child != node && !node->Sibling)
	{
		TreeNode *NewLast = node->Parent->Child;
		while(NewLast->Sibling != node)
			NewLast = NewLast->Sibling;
		NewLast->Sibling = NULL;
	}
	// Middle Child
	else
	{
		TreeNode *NewPlace = node->Parent->Child;
		while(NewPlace->Sibling != node)
			NewPlace = NewPlace->Sibling;
		NewPlace->Sibling = node->Sibling;
	}
	node->Parent = NULL;
	node->Sibling = NULL;
}
//! called if an event happened.
bool CGUITreeCtrl::SetSelected(TreeNode *node, bool IsAppend)
{
	if(Selected.size() == 1 && Selected[0] == node)
		return true;

	if( !IsAppend )
	{
		Selected.clear();
	}

	if(node == RootNode)	// Can't Select Root Node
		node = NULL;
	if(node && this->FindNode(node->ID) != node)	// Make sure this node exists on this tree
		return false;

	ui->unselectButtons();
	editor->updateControls();

	if(node)
	{
		Selected.push_back(node);
		editor->setSelectedNode(Selected[0]->SceneObject->m_SceneNode);
		//unfold tree view
		TreeNode* temp = Selected[0]->Parent;
		while(temp)
		{
			OpenNode(temp);
			temp = temp->Parent;
		}

		// check to see if we need to adjust the scrollbar
		int CX = -ScrollBarH->getPos() / 10 * ItemHeight;
		int CY = -ScrollBarV->getPos() / 10 * ItemHeight;
		int Indent = 0;
		bool FromChild = false;
		TreeNode *node = RootNode;
		do
		{
			// And we get the next node
			if(SubtreeVisible(node) && node->Child)
			{
				node = node->Child;
				Indent++;
				CX += ItemHeight;
			}
			else if(node->Sibling)
			{
				node = node->Sibling;
				FromChild = false;
			}
			else
			{
				TreeNode *next = node;
				while(!node->Sibling && node->Parent)
				{
					node = node->Parent;
					Indent--;
					CX -= ItemHeight;
				}
				if(node->Sibling)
					node = node->Sibling;
				else
					node = 0;
			}
			CY += ItemHeight;
			if (m_searchText.size() > 0 && node->LowerText.find(m_searchText.c_str()) == -1)
				CY -= ItemHeight;
		}
		while (node != Selected[0]);

		CY -= ItemHeight;

		core::rect<s32> AreaRect = AbsoluteRect;
		AreaRect.LowerRightCorner.X -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
		AreaRect.LowerRightCorner.Y -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);

		int minY = 0;
		int maxY = AreaRect.getHeight() - 2 * ItemHeight;
		if (CY < minY || CY >= maxY)
		{
			int need = (CY < minY ? CY - minY : CY - maxY);
			int delta = 10 * need / ItemHeight;
			ScrollBarV->setPos(ScrollBarV->getPos() + delta);
		}

		int minX = 0;
		int maxX = AreaRect.getWidth() - 2 * ItemHeight;
		if (CX < minX || CX >= maxX)
		{
			int need = (CX < minX ? CX - minX : CX - maxX);
			int delta = 10 * need / ItemHeight;
			ScrollBarH->setPos(ScrollBarH->getPos() + delta);
		}
	}
	else
	{
		editor->setSelectedNode(0);
	}

	return true;
}

void CGUITreeCtrl::OpenNode(TreeNode *node)
{
	if(!node || node->Open)
		return;
	if(Parent)
	{
		SEvent NewEvent;
		NewEvent.GUIEvent.Caller = this;
		NewEvent.EventType = irr::EET_GUI_EVENT;
		NewEvent.GUIEvent.Caller = this;
		NewEvent.GUIEvent.EventType = (irr::gui::EGUI_EVENT_TYPE)(EGET_TREEVIEW_OPENED_NODE + node->ID);
		node->Open = true;
		Parent->OnEvent(NewEvent);
	}
}
void CGUITreeCtrl::CloseNode(TreeNode *node)
{
	if(!node || !node->Open)
		return;
	if(Parent)
	{
		SEvent NewEvent;
		NewEvent.GUIEvent.Caller = this;
		NewEvent.EventType = irr::EET_GUI_EVENT;
		NewEvent.GUIEvent.EventType = (irr::gui::EGUI_EVENT_TYPE)(EGET_TREEVIEW_CLOSED_NODE + node->ID);
		node->Open = false;
		Parent->OnEvent(NewEvent);
	}
}

void CGUITreeCtrl::SetSelectedParent (TreeNode* parent)
{
	if (parent)
	{
		CSceneObject *pObj = editor->getSceneObjectFromID(parent->ID);
		if (!pObj) return;
		if (pObj->m_UserData->getAttributeAsString("!GameType") != "Geometry" &&
			pObj->m_UserData->getAttributeAsString("!GameType") != "Group" &&			
			pObj->m_UserData->getAttributeAsString("!GameType") != "EnemyGroup")
		{
			return;
		}
	}

	int savedpos = ScrollBarV->getPos();

	CMultiCommand* multi = new CMultiCommand;
	for (u32 i = 0; i < Selected.size(); ++i)
	{
		if(Selected[i]->Parent == parent) continue;
		CChangeTreeParentCommand* ch = new CChangeTreeParentCommand(Selected[i]->ID, Selected[i]->Parent->ID, parent ? parent->ID : -1);
		multi->addCommand(ch);
		multi->setDescription(ch->getDescription());
		ch->drop();
	}
	if (multi->getCommandCount() > 1)
		multi->setDescription(stringw("changed parents of ") + stringw(multi->getCommandCount()) + stringw(" objects"));
	if (multi->getCommandCount() > 0)
		editor->AddCommand(multi);
	else
		multi->drop();

	ScrollBarV->setPos(savedpos);
}

bool CGUITreeCtrl::OnEvent(const SEvent& event)
{
	switch(event.EventType)
	{
	case irr::EET_KEY_INPUT_EVENT:
	{
		if(Selected.size() == 1 && event.KeyInput.PressedDown)
		{
			TreeNode *NewSelected = NULL;
			switch(event.KeyInput.Key)
			{
				case KEY_LEFT:
					if(Selected[0]->Child && Selected[0]->Open)
					{
						CloseNode(Selected[0]);
						return true;
					}
				case KEY_UP:
					NewSelected = GetPrevVisibleNode(Selected[0]);
					if (m_searchText.size() > 0)
						while (NewSelected && NewSelected->LowerText.find(m_searchText.c_str()) < 0)
						{
							NewSelected = GetPrevVisibleNode(NewSelected);
						}
					break;

				case KEY_RIGHT:
					if(Selected[0]->Child && !Selected[0]->Open)
					{
						OpenNode(Selected[0]);
						return true;
					}
				case KEY_DOWN:
					NewSelected = GetNextVisibleNode(Selected[0]);
					if (m_searchText.size() > 0)
						while (NewSelected && NewSelected->LowerText.find(m_searchText.c_str()) < 0)
						{
							NewSelected = GetNextVisibleNode(NewSelected);
						}

					break;
			}
			if(NewSelected != NULL)
			{
				SetSelected(NewSelected);
			}
		}
		return true;	
	}
	case EET_GUI_EVENT:
		switch(event.GUIEvent.EventType)
		{
		case gui::EGET_SCROLL_BAR_CHANGED:
			break;
		case gui::EGET_ELEMENT_FOCUS_LOST:
			m_picked = false;
			break;
		case gui::EGET_ELEMENT_HOVERED:
			{
				//core::rect<s32> AreaRect = AbsoluteRect;
				//AreaRect.LowerRightCorner.X -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
				//AreaRect.LowerRightCorner.Y -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
				//if(AreaRect.isPointInside(p))
					Environment->setFocus(this);
				//else
				//{
				//	Environment->removeFocus(this);
				//	return false;
				//}
			}
		}
		break;
	case EET_MOUSE_INPUT_EVENT:
		{
			core::position2d<s32> p(event.MouseInput.X, event.MouseInput.Y);
			
			switch(event.MouseInput.Event)
			{
				case EMIE_MOUSE_WHEEL:
				{
					int pos = ScrollBarV->getPos();
					pos -= 40 * (s32)event.MouseInput.Wheel;
					if (pos < 0) pos = 0;
					if (pos > ScrollBarV->getMax()) pos = ScrollBarV->getMax();
					ScrollBarV->setPos(pos);
					return true;
				}

				case EMIE_LMOUSE_PRESSED_DOWN:
				{
					m_picked = false;
					if(RootNode->Child)
					{
						core::rect<s32> AreaRect = AbsoluteRect;
						AreaRect.LowerRightCorner.X -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
						AreaRect.LowerRightCorner.Y -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
						if(AreaRect.isPointInside(p))
							Environment->setFocus(this);
						else
						{
							Environment->removeFocus(this);
							return false;
						}
						p -= AbsoluteRect.UpperLeftCorner;
						int CY = -ScrollBarV->getPos() / 10 * ItemHeight;
						int Indent = 0;
						bool FromChild = false;
						TreeNode *node = RootNode;
						do
						{
							// And we get the next node
							if(node->Child && SubtreeVisible(node))
							{
								node = node->Child;
								Indent++;
							}
							else if(node->Sibling)
							{
								node = node->Sibling;
								FromChild = false;
							}
							else
							{
								TreeNode *next = node;
								while(!node->Sibling && node->Parent)
								{
									node = node->Parent;
									Indent--;
								}
								if(node->Sibling)
									node = node->Sibling;
								else
								{
									if (!g->eventReceiver->IsKeyDown(KEY_SHIFT))
										SetSelected(NULL);
									return true;
								}
							}

							CY += ItemHeight;
							if (m_searchText.size() > 0 && node->LowerText.find(m_searchText.c_str()) == -1)
								CY -= ItemHeight;
						}
						while(CY < p.Y);

						int CX = ScrollBarH->getPos();
						p.X += (ScrollBarH->getPos()/10)*16;
						if(p.X > (Indent-1) * ItemHeight)
						{
							if(p.X < (Indent) * ItemHeight)
							{
								if (node->Child) ToggleOpenNode(node);
							}
							else if(p.X >= (Indent) * ItemHeight && p.X < (Indent + 1) * ItemHeight)
							{
								bool setToVisible = !node->Checked;
								CMultiCommand* multi = new CMultiCommand;
								TreeNode* n = node;
								TreeNode* endNode = n;
								while (endNode && !endNode->Sibling)
								{
									endNode = endNode->Parent;
								}
								if (endNode) endNode = endNode->Sibling;
								while (n != endNode)
								{
									if(n->Checked!=setToVisible)
									{
										CSetVisibleCommand* vis = new CSetVisibleCommand(n->ID, setToVisible);
										multi->setDescription(vis->getDescription());
										multi->addCommand(vis);
										vis->drop();
									}
									n = GetNextNode(n);
								}
								editor->AddCommand(multi);
							}
							//else if( g->eventReceiver->IsKeyDown(KEY_KEY_Z) )
							//{
							//	SetSelected(node,true);
							//	m_lastClickedNode = node;
							//}
							else if ( g->eventReceiver->IsKeyDown(KEY_CONTROL))
							{
								SetSelected(node, true);
								editor->m_selection.push_back(editor->getSceneObjectFromID(node->ID));
							}
							else if (!g->eventReceiver->IsKeyDown(KEY_SHIFT))
							{
								if(Selected.size()==1)
								{
									if(Selected[0]==node)
									{
										void focusCameraOn (ISceneNode*);
										focusCameraOn(node->SceneObject->m_SceneNode);
										m_picked = true;
										position2di elem((Indent + 1) * ItemHeight, CY - ItemHeight);
										m_pickedOffset = elem - p + position2di(2, -1);
									}
									else
									{
										SetSelected(node);
										m_lastClickedNode = node;
									}
								}								
								else
								{//multi-selected or no selected
									SetSelected(node);
									m_lastClickedNode = node;
								}
							}
							else if (Selected.size() > 0)
							{
								TreeNode* start = Selected[0];
								if (Selected.size() > 1)
								{
									if (Selected.binary_search(m_lastClickedNode) >= 0)
									{
										start = m_lastClickedNode;
									}
									else
									{
										m_lastClickedNode = 0;
									}
								}

								Selected.clear();
								editor->setSelectedNode(0);

								array<TreeNode*> sel1;
								array<TreeNode*> sel2;
								sel1.push_back(start);
								sel2.push_back(start);
								while (sel1[sel1.size() - 1] != node && sel2[sel2.size() - 1] != node)
								{
									TreeNode* n1 = GetPrevVisibleNode(sel1[sel1.size() - 1]);
									if (m_searchText.size() > 0)
										while (n1 && n1->LowerText.find(m_searchText.c_str()) < 0)
										{
											n1 = GetPrevVisibleNode(n1);
										}
									if (n1) sel1.push_back(n1);
									TreeNode* n2 = GetNextVisibleNode(sel2[sel2.size() - 1]);
									if (m_searchText.size() > 0)
										while (n2 && n2->LowerText.find(m_searchText.c_str()) < 0)
										{
											n2 = GetNextVisibleNode(n2);
										}
									if (n2) sel2.push_back(n2);
								}
								array<TreeNode*>* newsel = &sel1;
								if (sel2[sel2.size() - 1] == node)
									newsel = &sel2;
								int savedpos = ScrollBarV->getPos();
								for (u32 i = 0; i < newsel->size(); ++i)
								{
									editor->toggleToSelection((*newsel)[i]->SceneObject->m_SceneNode);
								}
								ui->createSelectedObjectProperties();
								ScrollBarV->setPos(savedpos);
							}
						}
					}
					return true;
				}
				case EMIE_LMOUSE_LEFT_UP:

					if (m_picked && Selected.size() > 0)
					{
						m_picked = false;

						if(RootNode->Child)
						{
							core::rect<s32> AreaRect = AbsoluteRect;
							AreaRect.LowerRightCorner.X -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
							AreaRect.LowerRightCorner.Y -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
							if(AreaRect.isPointInside(p))
								Environment->setFocus(this);
							else
							{
								Environment->removeFocus(this);
								return false;
							}
							p -= AbsoluteRect.UpperLeftCorner;
							int CY = -ScrollBarV->getPos() / 10 * ItemHeight;
							int Indent = 0;
							bool FromChild = false;
							TreeNode *node = RootNode;
							do
							{
								// And we get the next node
								if(node->Child && SubtreeVisible(node))
								{
									node = node->Child;
									Indent++;
								}
								else if(node->Sibling)
								{
									node = node->Sibling;
									FromChild = false;
								}
								else
								{
									TreeNode *next = node;
									while(!node->Sibling && node->Parent)
									{
										node = node->Parent;
										Indent--;
									}
									if(node->Sibling)
										node = node->Sibling;
									else
									{
										return true;
									}
								}
								CY += ItemHeight;
								if (m_searchText.size() > 0 && node->LowerText.find(m_searchText.c_str()) == -1)
									CY -= ItemHeight;
							}

							while(CY < p.Y);
							
							p.X += (ScrollBarH->getPos()/10)*16;
							if (p.X > (Indent) * ItemHeight && Selected.binary_search(node) == -1)
							{
								SetSelectedParent(node);
							}
						}
					}

					m_picked = false;
					break;

				case EMIE_MOUSE_MOVED:
					break;
				case EMIE_RMOUSE_PRESSED_DOWN:
				{
					m_picked = false;
					int menuX = p.X;
					int menuY = p.Y;
					core::rect<s32> AreaRect = AbsoluteRect;
					AreaRect.LowerRightCorner.X -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
					AreaRect.LowerRightCorner.Y -= Environment->getSkin()->getSize(gui::EGDS_SCROLLBAR_SIZE);
					if(AreaRect.isPointInside(p))
						Environment->setFocus(this);
					else
					{
						Environment->removeFocus(this);
						return false;
					}

					if (Selected.size() > 0)
					{
						IGUIContextMenu* menu = g->guienv->addContextMenu(rect<s32>(menuX, menuY, menuX + 200, menuY + 200));
						if (Selected.size() == 1)
						{
							menu->addItem(L"Clone", CONTEXTMENU_ID_CLONE);
						}
						
						menu->addItem(L"Delete", CONTEXTMENU_ID_DELETE);
						menu->addItem(L"Lock", CONTEXTMENU_ID_LOCK);
						menu->addSeparator();
						menu->addItem(L"Move to root", CONTEXTMENU_ID_MOVE_TO_ROOT);
						if (Selected.size() == 1)
						{
							menu->addSeparator();
							menu->addItem(L"Up", CONTEXTMENU_ID_UP);
							menu->addItem(L"Down", CONTEXTMENU_ID_DOWN);
						}

						if (Selected.size() == 1)
						{
							menu->addSeparator();
							menu->addItem(L"New Group", CONTEXTMENU_ID_NEW_GROUP);

							if (Selected[0]->SceneObject->m_UserData->getAttributeAsString("!GameType") == "Camera")
							{
								menu->addItem(L"Activate Camera", CONTEXTMENU_ID_ACTIVATE_CAMERA);
							}
							else if (Selected[0]->SceneObject->m_UserData->getAttributeAsString("!GameType") == "Cinematic")
							{
								menu->addItem(L"Edit Cinematic", CONTEXTMENU_ID_EDIT_CINEMATIC);
								menu->addItem(L"Adjust Cinematic", CONTEXTMENU_ID_ADJUST_CINEMATIC);
							}
							menu->addSeparator();
						}

						if (editor->m_bLinkRoomMode)
						{
							menu->addItem(L"Stop linking", CONTEXTMENU_ID_LINK_TO);
						}
						else
						{
							menu->addItem(L"Link to", CONTEXTMENU_ID_LINK_TO);
						}
					}

					return true;
				}
			}
		}
		break;
	}

	return Parent ? Parent->OnEvent(event) : false;
}

bool CGUITreeCtrl::SetOverrideFont(IGUIFont *font)
{
	if(font == OverrideFont)
		return false;
	if(OverrideFont)
		OverrideFont->drop();
	OverrideFont = font;
	if(OverrideFont)
		OverrideFont->grab();	
	recalculateItemHeight();
	return true;
}

IGUIFont *CGUITreeCtrl::GetOverrideFont()
{
	return OverrideFont;
}

void CGUITreeCtrl::AddDummyNode()
{
	InsertNode("New Node", Selected.size() > 0 ? Selected[0] : 0);	
}

void CGUITreeCtrl::InsertToSelectedNode(core::stringw Text, irr::s32 ID, CSceneObject *SceneObject)
{
	InsertNode(Text, Selected.size() > 0 ? Selected[0] : 0, ID, SceneObject, SceneObject->m_SceneNode->isVisible());
}

void CGUITreeCtrl::InsertToParentNode(TreeNode *Parent, core::stringw Text, irr::s32 ID, CSceneObject *SceneObject)
{
	InsertNode(Text, Parent, ID, SceneObject, SceneObject->m_SceneNode->isVisible());
}

void CGUITreeCtrl::SetSearchText (const core::stringw& text)
{
	m_searchText = text;
	m_searchText.make_lower();
}

namespace irr
{
	namespace gui
	{
		int GetDepth (TreeNode* node)
		{
			int depth = 0;
			while (node->Parent)
			{
				++depth;
				node = node->Parent;
			}
			return depth;
		}
	}
}

bool CGUITreeCtrl::SubtreeVisible (TreeNode* node)
{
	return node->Open || m_searchText.size() > 0;
}

void CGUITreeCtrl::updateSelected ()
{
	Selected.clear();
	for (u32 i = 0; i < editor->m_selection.size(); ++i)
	{
		TreeNode* node = FindNode(editor->m_selection[i]->m_SceneNode->getID());
		Selected.push_back(node);
		while (node->Parent && !node->Parent->Open)
		{
			node->Parent->Open = true;
			node = node->Parent;
		}
	}
}
void CGUITreeCtrl::updateSelectedFromList(IGUIListBox* list)
{
	Selected.clear();
	editor->m_selection.clear();
	for (u32 i = 0; i <((CListBox*)list)->SelectedList.size(); ++i)
	{		
		int sel = ((CListBox*)list)->SelectedList[i];
		int id = ((CListBox*)list)->getTreeNodeID(sel);
		TreeNode* node = FindNode(id);		
		Selected.push_back(node);
		editor->m_selection.push_back(node->SceneObject);
		while (node->Parent && !node->Parent->Open)
		{
			node->Parent->Open = true;
			node = node->Parent;
		}
	}
}